package insertsort

//InsertSort 插入排序
//平均：O(n^2),最坏：O(n^2), 最好：O(n)
//稳定的排序，只交换相邻元素
func InsertSort(nums []int) []int {
	ln := len(nums)
	for i := 0; i < ln-1; i++ {
		for j := i+1; j > 0; j-- {
			if nums[j] < nums[j-1] {
				nums[j],nums[j-1] = nums[j-1],nums[j]
			} else {
				break;
			}
		}
	}
	return nums
}